﻿#pragma once
#include<map>
#include<iostream>
#include<vector>
using namespace std;
// 枚举值表⽰颜⾊
enum Colour
{
	RED,
	BLACK
};
template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;
	RBTreeNode(const T& data) :_data(data), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};
		
template<class T,class Ref,class Ptr>//const int,const int*,const int& 
class rbtree_iterator
{
	typedef RBTreeNode<T> Node;
	typedef rbtree_iterator<T, Ref, Ptr> Self;
public:
	rbtree_iterator(Node* node , Node * root) :_node(node), _root(root)
	{}
	Ptr operator*()//T可能是pair或者k
	{
		return  _node->_data;
	}
	Ref operator->()
	{
		return &(_node->_data);
	}
	Self& operator--()
	{
		if (_node == nullptr)
		{
			Node* cur = this->_root;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			if (_node->_left)
			{
				//左不为空去访问左树最大节点
				Node* cur = _node->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_node = cur;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent&&parent->_left == cur)
				{
					cur = parent;
					parent = cur;
				}
				_node = parent;
			}
		}
		return *this;
	}
	Self& operator++()//进里面的头迭代器一定不为空
	{
		if (_node->_right)
		{
			//去找右树最左边的节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent&&parent->_right == cur)//更新到最后根节点可能为空指针
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;//如果parent是空那么此时的节点一定是最后一个节点在加加就是end也就是空指针

		}
		return *this;
	}
	bool operator!=(const Self& s)const
	{
		return this->_node != s._node;
	}
	bool operator==(const Self& s)const
	{
		return this->_node == s._node;
	}

private:
	Node *_node;
	Node * _root;//为了end--时进行判断end--然后从根节点开始找到最右边的数
};
//int const int /int int
template <class K, class T,class keyofcon>//int ，const int 
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	//原来的就是int int* int&
	typedef rbtree_iterator<T,  T*,  T&> Iterator;//const int /const int* /const int &
	typedef rbtree_iterator<T, const T*, const T&> ConstIterator;
	keyofcon keyof;

	Iterator Begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur,_root);//调用隐式构造
	}
	Iterator End()
	{
		return Iterator(nullptr,_root);
	}
	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return { Iterator(_root,_root),true };
		}
		Node* cur = _root;
		Node* parent = _root;
		while (cur)
		{
			if (keyof(data) > keyof(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (keyof(data) < keyof(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return { Iterator(cur,_root),false };//插入失败返回已经存在的迭代器
			}
		}
		cur = new Node(data);
		Node* tem = cur;//记录插入节点
		cur->_col = RED;
		if (keyof(parent->_data) > keyof(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_left == cur)
					{
						RoteR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RoteL(parent);
						RoteR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RoteL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RoteR(parent);
						RoteL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//防止一直向上处理到parent是空时
		return {Iterator(tem,_root),true};
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else
				return cur;
		}
		return nullptr;
	}
	void RoteR(Node* parent)
	{
		Node* prev = parent->_parent;
		Node* sub = parent;
		Node* subl = sub->_left;
		Node* sublr = subl->_right;
		sub->_left = sublr;
		if (sublr) sublr->_parent = sub;
		subl->_right = sub;
		sub->_parent = subl;
		
		if (prev == nullptr)
		{
			_root = subl;
			_root->_parent = nullptr;
		}
		else
		{
			if (prev->_right == parent)
			{
				prev->_right = subl;
				
			}
			else
			{
				prev->_left = subl;
				
			}
			subl->_parent = prev;
		}
	}
	void RoteL(Node* parent)
	{
		Node* prev = parent->_parent;

		Node* sub = parent;
		Node* subr = sub->_right;
		Node* subrl = subr->_left;

		sub->_right = subrl;
		if (subrl) subrl->_parent = sub;
		subr->_left = sub;
		sub->_parent = subr;
		if (prev == nullptr)
		{
			_root = subr;
			_root->_parent = nullptr;
		}
		else
		{
			if (prev->_left == parent)
			{
				prev->_left = subr;
				subr->_parent = prev;
			}
			else
			{
				prev->_right = subr;
				subr->_parent = prev;
			}
		}

	}
	
	int Height()
	{
		 return _height(_root);
	}
	int Size()
	{
		return _size(_root);
	}
private:
	void _inorder(Node* root)
	{
		if (root == nullptr) return;
		_inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_inorder(root->_right);
	}
	int _height(Node* root)
	{
		if (root == nullptr) return 0;
		int left = _height(root->_left);
		int right = _height(root->_right);
		return left > right ? left + 1: right + 1;
	}
	int _size(Node* root)
	{
		if (root == nullptr) return 0;
		int left = _size(root->_left);
		int right = _size(root->_right);
		return left + right + 1;
	}
	Node* _root=nullptr;
};
